public class expensive_loop_invariant {
  static int incr(int x) { return x + 1; }

  // incr will not be hoisted since it is cheap(constant time)
  static void foo_linear(int size) {
    int x = 10;
    for (int i = 0; i < size; i++) {
      incr(x); // constant call, don't hoist
    }
  }

  // call to foo_linear will be hoisted since it is expensive(linear in size).
  static void symbolic_expensive_hoist(int size) {
    for (int i = 0; i < size; i++) {
      foo_linear(size); // hoist
    }
  }

  public static void loop() { symbolic_expensive_hoist(1000000000); }

  public static void cheap_loop() {
    int size = 1000000000;
    for (int i = 0; i < size; i++) {
      int x = 10;
      for (int j = 0; j < size; j++) {
        incr(x); // constant call, don't hoist
      }
    }
  }
}
